:- module(tp2, [distHam/3, distPref/3, distEd/3]).

%------------------------------------------------
%              Predicados Auxiliares
%------------------------------------------------

% Solo vamos a trabajar con cadenas de 0's y 1's
elemValido(0).
elemValido(1).

% Determina los Z que estan entre X e Y inclusive
entre(X, Y, X) :- X =< Y.
entre(X, Y, Z) :- X < Y, N is X+1, entre(N, Y, Z).

% Determina/genera una cadena compuesta por elementos validos
cadenaValidaDeLong([], 0).
cadenaValidaDeLong([X|Xs], N) :-
    ground(N), N>0, M is N-1,
    elemValido(X), cadenaValidaDeLong(Xs, M).
cadenaValidaDeLong([X|Xs], N) :-
    not(ground(N)), ground(X),
    elemValido(X), cadenaValidaDeLong(Xs, M), N is M+1.
cadenaValidaDeLong([X|Xs], N) :-
    not(ground(N)), not(ground(X)),
    cadenaValidaDeLong(Xs, M), elemValido(X), N is M+1.

%------------------------------------------------
%              Distancia de Hamming
%------------------------------------------------
distHam([], [], 0).
distHam([X|Xs], [X|Ys], N) :- elemValido(X), distHam(Xs, Ys, N).
distHam([X|Xs], [Y|Ys], N) :- elemValido(X), elemValido(Y), X \= Y, distHam(Xs, Ys, NAnt), N is NAnt + 1.


%------------------------------------------------
%              Distancia de Prefijos
%------------------------------------------------

% Dadas 2 cadenas, encuentra el prefijo comun mas largo entre ellas
prefijoComunMasLargo([], [], []).
prefijoComunMasLargo([_|Xs], [], []) :- prefijoComunMasLargo(Xs, [], []).
prefijoComunMasLargo([], [_|Xs], []) :- prefijoComunMasLargo([], Xs, []).
prefijoComunMasLargo([X|_], [Y|_], []) :- X \= Y.
prefijoComunMasLargo([X|Xs], [X|Ys], [X|Zs]) :- prefijoComunMasLargo(Xs, Ys, Zs).

% distPref(+L1, ?L2, ?L3)
distPref(X, Y, N) :- ground(N),
	cadenaValidaDeLong(X,Nx),
	Nmax is Nx + N,
	entre(0, Nmax, Ny),
	cadenaValidaDeLong(Y,Ny),
	prefijoComunMasLargo(X, Y, Z), 
	cadenaValidaDeLong(Z, Nz), 
	N is (Nx - Nz) + (Ny - Nz).
distPref(X, Y, N) :- not(ground(N)),
	cadenaValidaDeLong(X,Nx),
	cadenaValidaDeLong(Y,Ny),
	prefijoComunMasLargo(X, Y, Z), 
	cadenaValidaDeLong(Z, Nz), 
	N is (Nx - Nz) + (Ny - Nz).


%------------------------------------------------
%              Distancia de Edicion
%------------------------------------------------

distEd([], Y, N) :- cadenaValidaDeLong(Y,N).
distEd(X, [], N) :- X \= [], cadenaValidaDeLong(X,N).
distEd([X|Xs], [Y|Ys], N) :- ground(N), ground([Y|Ys]), elemValido(X), elemValido(Y),
			     distEd(Xs, Ys, N1), distEd(Xs, [Y|Ys], N2), distEd([X|Xs], Ys, N3),
                             Nambos is N1 + abs(X - Y), Nder is N2 + 1, Nizq is N3 + 1,				
			     Nmin is min(Nambos, Nizq), N is min(Nmin, Nder).  
distEd([X|Xs], [Y|Ys], N) :- ground(N), not(ground([Y|Ys])),elemValido(X), elemValido(Y),
			     cadenaValidaDeLong([X|Xs],Nx), 
			     Nmaxcota is N + Nx , 
			     Nmincota is max(0, N - Nx),
			     entre(Nmincota, Nmaxcota, Ny), cadenaValidaDeLong(Ys, Ny),
			     distEd(Xs, Ys, N1), distEd(Xs, [Y|Ys], N2), distEd([X|Xs], Ys, N3),
                             Nambos is N1 + abs(X - Y), Nder is N2 + 1, Nizq is N3 + 1,				
			     Nmin is min(Nambos, Nizq), N is min(Nmin, Nder).  
distEd([X|Xs], [Y|Ys], N) :- not(ground(N)), ground([Y|Ys]), elemValido(X), elemValido(Y),
			     cadenaValidaDeLong([X|Xs],Nx), cadenaValidaDeLong([Y|Ys],Ny),
			     Ncotamax is max(Nx, Ny),
			     Ncotamin is abs(Nx - Ny),
			     entre(Ncotamin, Ncotamax, N),
			     distEd(Xs, Ys, N1), distEd(Xs, [Y|Ys], N2), distEd([X|Xs], Ys, N3),
                             Nambos is N1 + abs(X - Y), Nder is N2 + 1, Nizq is N3 + 1,				
			     Nmin is min(Nambos, Nizq), N is min(Nmin, Nder).  
distEd([X|Xs], [Y|Ys], N) :- not(ground(N)), not(ground([Y|Ys])), elemValido(X), elemValido(Y),
			     distEd(Xs, Ys, N1), distEd(Xs, [Y|Ys], N2), distEd([X|Xs], Ys, N3),
                             Nambos is N1 + abs(X - Y), Nder is N2 + 1, Nizq is N3 + 1,				
			     Nmin is min(Nambos, Nizq), N is min(Nmin, Nder).  


